#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& candidates, int target, int aim, int pos)
{
	if (aim > target)
	{
		return;
	}
	if (aim == target)
	{
		ans.push_back(path);
		return;
	}

	for (int i = pos; i < candidates.size(); i++)
	{
		path.push_back(candidates[i]);
		aim += candidates[i];
		dfs(candidates, target, aim, i);
		aim -= candidates[i];
		path.pop_back();
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
{
	dfs(candidates, target, 0, 0);
	return ans;
}
